← All Articles

[SW Expert Academy] 4366. 정식이의 은행업무

Posted on

문제 :

삼성은행의 신입사원 정식이는 실수를 저질렀다.

은행 업무가 마감되기 직전인 지금, 송금할 금액을 까먹고 말았다.

하지만 다행스럽게도 정식이는 평소 금액을 2진수와 3진수의 두 가지 형태로 기억하고 다니며, 기억이 명확하지 않은 지금조차 2진수와 3진수 각각의 수에서 단 한 자리만을 잘못 기억하고 있다는 것만은 알고 있다.

예를 들어 현재 기억이 2진수 1010과 3진수 212을 말해주고 있다면 이는 14의 2진수인 1110와 14의 3진수인 112를 잘못 기억한 것이라고 추측할 수 있다.

정식이는 실수를 바로잡기 위해 당신에게 부탁을 하였다.

정식이가 송금액을 추측하는 프로그램을 만들어주자.

( 단, 2진수와 3진수의 값은 무조건 1자리씩 틀리다. 추측할 수 없는 경우는 주어지지 않는다. )

image


입력 :

10개 이하의 테스트 케이스가 주어진다.

첫 번째 줄에는 테스트케이스의 개수가 주어진다.

하나의 케이스는 두 줄로 되어있다.

각 케이스의 첫 번째 줄은 정식이가 기억하는 송금액의 2진수 표현, 두 번째 줄은 송금액의 3진수 표현이 주어진다.

(3 ≤ 2진수, 3진수의 자릿수 <40)


출력 :

원래 송금하기로 하였던 금액을 케이스마다 한 줄에 하나씩 출력한다.



풀이 :

처음에 3^40의 수의 범위를 보고 long 형으로 표현이 가능한가 약간 헷갈렸던 것 같다.

우선 답의 범위는 모두 long long 범위로 표현이 가능하기 때문에 문제가 엄청 까다로워지진 않았던 것 같다.

쉬프트 연산자 혹은 2진수, 3진수의 자릿수를 효율적으로 바꿔서 체크해보는 방법만 잘 캐치하면 문제는 쉽게 해결이 가능했던 것 같다.

우선 내가 사용한 방식은, 입력받은 2진수 3진수의 10진수 값을 저장해두고

가능한 2진수 답 (2진수 자리 중 하나의 숫자를 바꾼 값)을 모두 set에 저장한 후 3진수 답(3진수 자리 중 하나의 숫자를 바꾼 값)을 구해 하나씩 set에 존재하는지 체크해서 존재하면 해당하는 숫자를 반환하는 형태로 코드를 꾸렸다.



코드 :

코드 보기/접기 
#include<iostream>
#include<string>
#include<cmath>
#include<set>
 
#define ll long long
 
using namespace std;
 
ll testCase() {
    set<ll> set;
    ll originthird = 0, originsec = 0;
    string secstr, thirdstr;
    cin >> secstr >> thirdstr;
    int thirdlength = thirdstr.length(), seclength = secstr.length();
     
    for(int i=0; i<seclength; i++) 
        originsec += (1<<i) * (secstr[seclength - i - 1] - '0');
    for(int i=0; i<thirdlength; i++)
        originthird += pow(3, i) * (thirdstr[thirdlength - i - 1] - '0');
     
    set.insert(originsec);
    for(int i=0; i<seclength; i++)
        set.insert(originsec - (1<<i) * (secstr[seclength - i - 1] - '0') + ((secstr[seclength - i - 1] == '0') ? (1<<i):0));
     
    for(int i=0; i<thirdlength; i++)
        for(int j=0; j<3; j++) {
            if(thirdstr[thirdlength - i - 1] - '0' == j) continue;
            ll chnum = originthird - pow(3, i) *  (thirdstr[thirdlength - i - 1] - '0') + pow(3, i) * j;
            if(set.find(chnum) != set.end()) return chnum;
        }
}
 
int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin>>T;
     
    for(test_case = 1; test_case <= T; ++test_case)
    {
        cout << '#' << test_case << ' ' << testCase() << '\n';
    }
    return 0;
}


AlgorithmalgorithmSW ExpertC++